Herzlich willkommen!

Wir befassen uns heute, wenn wir denn so weit kommen, mit zwei Themen.

Ich spreche jetzt leise weiter.

Also, wie angekündigt, wir befassen uns mit zwei Themen.

Zum einen mit asymptotischer Notation.

Und zum anderen, wenn wir so weit kommen, mit dem Maschinenmodell.

Das Maschinenmodell ist dann im Wesentlichen nur eine Erinnerung an die Random Access Machine, die aus BFS bekannt sein dürfte.

Das trifft zu. Random Access Machine, Begriff aus BFS.

Also, wer kennt die nicht?

Einer.

Das ist ja nichts Schlimmes.

Also, wir machen es nochmal sowieso, wie gesagt.

Okay, also, erster größerer Block, asymptotische Notation beziehungsweise...

...asymptotisches Verhalten.

Das heißt, wir sehen uns an, das Verhalten eines Programms, an dem uns typischerweise nur die eine oder andere Form von Ressourcenverbrauch interessiert.

Ressourcen meistens Zeit, manchmal Speicherplatz, heute modern Bandbreite, das werden wir nicht tun.

Das heißt also...

Naja, der Ressourcenverbrauch, der ist natürlich nicht bei jedem Aufruf des Programms derselbe.

Das hängt von verschiedenen Dingen ab, was so ein Programm an Ressourcen verbraucht.

Wir interessieren uns für die Abhängigkeit des Ressourcenverbrauchs vom Input.

A, B, H, Abkürzung für Abhängigkeit.

V, Abkürzung für von, durchweg.

Ja, im Abhängigkeit vom Input.

Naja, das wäre natürlich ein hartes Geschäft, wenn wir das wirklich so feingranular durchziehen wollten.

Wir haben also irgendeinen Inputraum, was weiß ich, die Menge der Strings oder sowas, die Menge der Listen, die wir sortieren wollen.

Und, naja, es ist eben von Liste zu Liste aufwendig, sie zu sortieren.

Und da hätten wir also unseren Spaß, wenn wir eine Funktion angeben wollten, die also in tatsächlich in geschlossener Form und in Abhängigkeit direkt von der Liste uns angibt, wie viel Zeit da verbraucht wird.

Wir müssen also geeignet abstrahieren.

Die Abstraktion, die man meistens nimmt, ist, dass man den Input reduziert auf seine Größe.

Also man braucht eine Abstraktion des Inputs, zum Beispiel Größe.

Das ist diejenige Abstraktion, die weite Teile der Algorithmenanalyse und Komplexitätstheorie durchdringt.

Und sie klingt auch erst mal zwingend. Also je größer ein Problem ist, das man mir vorwirft, umso schwieriger ist es.

Das ist aber so ein bisschen auch eine Täuschung.

Es gibt durchaus andere denkbare Abstraktionen.

Und es ist durchaus gelegentlich sinnvoll, sich auch andere Abstraktionen anzusehen.

Wenn man Grafalgorithmen macht, beispielsweise, gibt es oft Maße, die also einem wesentlich mehr über die Schwierigkeit des Problems sagen, als die Größe des Grafen, sagen wir mal Baumbreite oder solche Maße.

Was fiel mir eben noch ein? Das zweite Beispiel habe ich gerade wieder vergessen.

Es gibt jedenfalls durchaus andere Parameter, die ich aus dem Input rausziehen kann als eine Abstraktion, von der in wesentlich vielsagenderer Weise die Komplexität, also die Laufzeit des Programms zum Beispiel, abhängt.

Das Erste, was einem einfällt und das, was eben meistens gemacht wird, ist einfach die Größe zu nehmen.

Ja, Sat-Problem fiel mir noch ein. Man misst die Größe eines Sat-Problems typischerweise einfach in der Anzahl Klauseln, die ich da rein packe.

Sat-Problem geläufig aus BFS.

Das ist, wenn man sich anguckt, die sogenannte Phase Transition, die ungefähr so aussieht, ist das auch nicht so ganz das richtige Maß vielleicht.

Diese Phase Transition, man sieht hier Anzahl, was ist da genau aufgetragen? Also in einer Richtung sind viele Variablen im Verhältnis zu Klauseln und hier wird es umgekehrt.

Wenn ich also viele Variablen habe, dann habe ich viel, woran ich drehen kann, dann ist also ein Sat-Problem leicht erfüllbar und in der Tat sind die Satzsäuber dann auch schnell.

Wenn ich sehr wenig Variablen habe im Vergleich zu meiner Anzahl Klauseln, dann habe ich ein großes Problem, meine Klauseln zu erfüllen, weil ich wenig Freiheitsgrade habe, dann sind die Probleme meistens unerfüllbar und wiederum sind die Satzsäuber schnell.

Das heißt, die Schwierigkeit eines Sat-Problems ist in Wirklichkeit die Nähe zu diesem Phasenübergang hier, wo sich das Verhältnis zwischen Anzahl Variablen und Anzahl Klauseln auf so einen Mittelwert einpendelt.

Das wäre also in Wirklichkeit das Maß für die Schwierigkeit eines Sat-Problems und nicht seine reine Größe.

Das ist natürlich auch viel schwieriger zu analysieren, deswegen Größe.

Dazu müssen wir ein paar Larnen vergeben für die Dinge, mit denen wir hier antieren.

Wir sagen, wir hängen ab von den Inputs. Gut, damit wir da einen Bezeichner für haben, nehmen wir mal I als Name für die Menge der Inputs.